Zosia

Limit pamięci: 128 MB

Mała Zosia urządza przyjęcie urodzinowe. Sporządziła wstępną listę swoich znajomych z przedszkola, których chciałaby zaprosić. Dzieci są jednak bardzo wymagające. Maja powiedziała, że przyjdzie, ale tylko jeśli na przyjęciu nie będzie Kamilki i Emilki, które w zeszłym tygodniu zabrały jej lalkę. Mały Krzyś bawi się tylko z Zosią oraz Kamilką, i nie chce widzieć na przyjęciu innych dzieci. I tak dalej

Zosia mówi, że przyjęcie jest udane, jeżeli żaden spośród gości nie ma nic przeciwko obecności pozostałych gości. Zosia postanowiła, że nie zaprosi niektórych dzieci, aby przyjęcie było udane. Z drugiej strony, Zosia chciałaby zaprosić jak najwięcej dzieci. Uznała, że jeśli nie będzie mogła zaprosić przynajmniej dzieci, to w ogóle nie urządzi przyjęcia.

Zadanie

Pomóż małej Zosi! Napisz program, który:

• wczyta ze standardowego wejścia liczbę wszystkich znajomych Zosi, liczbę oraz opis wymagań dzieci,
• sprawdzi, czy można zaprosić co najmniej dzieci tak, aby przyjęcie było udane,
• jeżeli nie jest to możliwe, to wypisze na standardowe wyjście słowo NIE; jeżeli jest to możliwe, to znajdzie i wypisze na standardowe wyjście najliczniejszą grupę dzieci, które można zaprosić na przyjęcie, tak aby było ono udane.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite nieujemne, oddzielone pojedynczym odstępem: - liczbę wszystkich znajomych Zosi (), - minimalną liczbę dzieci, które Zosia chce zaprosić na przyjęcie (). Dzieci są ponumerowane liczbami od do .

Kolejne wiersze zawierają opis wymagań dzieci. W drugim wierszu znajduje się jedna liczba całkowita , . Każdy z kolejnych wierszy zawiera parę liczb całkowitych , oddzielonych pojedynczym odstępem (, ). Możesz założyć, że każda para (uporządkowana) pojawia się na wejściu co najwyżej raz. Para oznacza, że dziecko o numerze nie chce spotkać na przyjęciu dziecka o numerze .

Wyjście

Jeżeli nie jest możliwe zaproszenie na przyjęcie dzieci, tak aby było ono udane, to pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać tylko jedno słowo: NIE.

Jeżeli jest to możliwe, to pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - maksymalną liczbę dzieci, które można zaprosić na przyjęcie, tak aby było ono udane. Drugi wiersz standardowego wyjścia powinien wówczas zawierać numery dzieci, które należy zaprosić, podane w rosnącej kolejności i pooddzielane pojedynczymi odstępami. Jeżeli istnieje wiele poprawnych wyników, Twój program powinien wypisać dowolny z nich.

Przykład

Dla danych wejściowych:

9 4
12
9 6
4 6
7 9
1 2
2 1
9 7
7 6
4 5
7 8
8 9
3 4
4 3

poprawną odpowiedzią jest:

5
1 3 5 6 8

Autor zadania: Łukasz Kowalik.